/*
练习14-1 B+树的查找
分数 25
作者 陈越
单位 浙江大学

按照 101 计划《数据结构》主教材中的定义，B+
树的叶结点中存储的是指向原始记录的指针，每个记录中有一个关键码，所有记录按关键码的顺序（本题定义为升序）存储在叶结点中。上面各层结点中的关键码均是下一层相应结点中最大关键码的复写。
本题请你实现 B+ 树的查找功能，即对于给定的关键码 key，返回指向 key
所在记录的指针。 函数接口定义：

Position FindLeaf(BTreeHead btree, ElemSet key);

TElemSet SearchBTree(BTreeHead btree, ElemSet key);

其中各种数据类型的定义如下：

typedef int ElemSet;  //  默认元素为整数
typedef struct RecordNode {
    ElemSet key; //  关键码
    //  其他属性由用户自定义
} Records;

typedef Records *TElemSet;
typedef struct BTreeNode *Position; //  树结点指针是元素的位置
typedef struct BTreeNode *BTree;
struct BTreeNode {
    int num_keys;      //  关键码个数
    TElemSet *data;    //  存储带关键码的记录的数组
    BTree *children;   //  孩子指针数组
    BTree parent;      //  父结点指针
    bool leaf;         //  叶结点标识
    BTree pre;         //  叶结点的前一个结点指针
    BTree next;        //  叶结点的下一个结点指针
};

typedef struct HeadNode *BTreeHead; //  B+ 树的头指针
struct HeadNode {
    BTree root;  //  B+树的根结点
    BTree first; //  指向具有最小关键码的第一个叶结点
    int order;   //  B+树的阶
};

函数接口定义中：

    ElemSet 是用户定义的数据类型，例如 int、double 或者 char 等，要求可以通过
>、==、< 进行比较，此处定义为整型。 带关键码的原始记录类型为结构体
Records，包含关键字 key 以及其它内容。 B+ 树的类型 BTree 是指向结构体 BTreeNode
的指针。一个 B+ 树结点包含存储数据（即指向原始记录的指针，类型命名为
TElemSet）的数量 num_keys、存储数据的数组 data、存储子树指针的数组
children、父结点指针 parent，此外，如果是叶结点，则标识 leaf 值为
true，与此同时，叶结点被存储为一个双向链表，有双向指针 pre 和 next
分别指向其前一个、后一个叶结点。 B+ 树的头结点 BTreeHead 存储根结点的位置
root、叶结点链表的第一个结点位置 first，以及树的阶 order。

要求实现的函数有两个：
1、FindLeaf 应在 btree 中寻找包含了关键码 key
的叶结点。如果这个结点存在，则返回该结点的位置（即指向该叶结点的指针）；如果不存在，则返回可以插入这个关键码的叶结点的位置。当然这样的位置可能不唯一，如果有两种选择，规定总是选择靠右边的结点。
2、SearchBTree 应在 btree 中寻找以 key
为关键码的原始记录，返回其位置。如果记录不存在，则返回空指针 NULL。

注意：两个函数都默认 btree 不是 NULL。

输入样例：

3 9
3 1 4 5 9 2 8 7 0
7
-1 0 3 5 6 8 10

输出样例：

Not Found
0
3
5
Not Found
8
Not Found
*/

#include <stdio.h>
#include <stdlib.h>

typedef enum { false, true } bool;
typedef int ElemSet; /* 默认元素为整数*/
typedef struct RecordNode {
    ElemSet key; /* 关键码 */
    /* 其他属性由用户自定义 */
} Records;

typedef Records *TElemSet;
typedef struct BTreeNode *Position; /* 树结点指针是元素的位置 */
typedef struct BTreeNode *BTree;
struct BTreeNode {
    int num_keys;    /* 关键码个数 */
    TElemSet *data;  /* 存储带关键码的记录的数组 */
    BTree *children; /* 孩子指针数组 */
    BTree parent;    /* 父结点指针 */
    bool leaf;       /* 叶结点标识 */
    BTree pre;       /* 叶结点的前一个结点指针 */
    BTree next;      /* 叶结点的下一个结点指针 */
};
typedef struct HeadNode *BTreeHead; /* B+ 树的头指针 */
struct HeadNode {
    BTree root;  /* B+ 树的根结点 */
    BTree first; /* 指向具有最小关键码的第一个叶结点 */
    int order;   /* B+ 树的阶 */
};

BTreeHead InitBTree(int order) { /* 初始化空的order阶B+树 */
    BTreeHead btree;

    btree = (BTreeHead)malloc(sizeof(struct HeadNode));
    btree->root = NULL;
    btree->first = NULL;
    btree->order = order;

    return btree;
}

Position FindLeaf(BTreeHead btree, ElemSet key);
TElemSet SearchBTree(BTreeHead btree, ElemSet key);

// 创建一个新的 B+ 树结点
BTree CreateNode(int order, bool leaf) {
    BTree node = (BTree)malloc(sizeof(struct BTreeNode));
    node->num_keys = 0;
    // 为关键码和子树分配空间, 插入时可能会超过阶数，所以需要额外一个空间
    node->data = (TElemSet *)calloc(order + 1, sizeof(TElemSet));
    node->children = (BTree *)calloc(order + 2, sizeof(BTree));
    node->parent = NULL;
    node->leaf = leaf;
    node->pre = NULL;
    node->next = NULL;
    return node;
}

// 将关键码插入到结点中
void InsertToNode(BTreeHead btree, BTree node, TElemSet x, BTree child) {
    int i = node->num_keys - 1;
    
    // 找到插入位置
    while (i >= 0 && x->key < node->data[i]->key) {
        node->data[i + 1] = node->data[i];
        if (!node->leaf) {
            node->children[i + 2] = node->children[i + 1];
        }
        i--;
    }
    
    // 插入关键码
    node->data[i + 1] = x;
    if (!node->leaf) {
        node->children[i + 2] = child;
        if (child != NULL) {
            child->parent = node;
        }
    }
    node->num_keys++;
}

// 分裂结点
void SplitNode(BTreeHead btree, BTree node) {
    int order = btree->order;
    int split = (order + 1) / 2;
    
    // 创建新结点
    BTree newNode = CreateNode(order, node->leaf);
    newNode->parent = node->parent;
    
    // 将后半部分关键码和子树移动到新结点
    for (int i = split; i < node->num_keys; i++) {
        newNode->data[i - split] = node->data[i];
        newNode->children[i - split + 1] = node->children[i + 1];
        if (newNode->children[i - split + 1] != NULL) {  // 检查是否为 NULL
            newNode->children[i - split + 1]->parent = newNode;
        }
    }
    newNode->num_keys = node->num_keys - split;
    node->num_keys = split;
    
    // 如果是叶结点，更新链表
    if (node->leaf) {
        newNode->next = node->next;
        if (node->next != NULL) {
            node->next->pre = newNode;
        }
        node->next = newNode;
        newNode->pre = node;
    }
    
    // 将中间关键码插入到父结点
    if (node->parent == NULL) {
        // 如果当前结点是根结点，创建新的根结点
        BTree newRoot = CreateNode(order, false);
        newRoot->data[0] = node->data[split];
        newRoot->children[0] = node;
        newRoot->children[1] = newNode;
        newRoot->num_keys = 1;
        node->parent = newRoot;
        newNode->parent = newRoot;
        btree->root = newRoot;
    } else {
        // 否则将中间关键码插入到父结点
        InsertToNode(btree, node->parent, node->data[split], newNode);
        if (node->parent->num_keys > order) {
            SplitNode(btree, node->parent);
        }
    }
}

// 插入关键码到 B+ 树
BTreeHead InsertBTree(BTreeHead btree, TElemSet x) {
    if (btree->root == NULL) {
        // 如果树为空，创建根结点
        btree->root = CreateNode(btree->order, true);
        btree->first = btree->root;
        InsertToNode(btree, btree->root, x, NULL);
    } else {
        // 找到插入位置
        Position leaf = FindLeaf(btree, x->key);
        InsertToNode(btree, leaf, x, NULL);
        
        // 如果叶结点关键码数量超过阶数，进行分裂
        if (leaf->num_keys > btree->order) {
            SplitNode(btree, leaf);
        }
    }
    return btree;
}

int main(void) {
    BTreeHead btree;
    TElemSet x;
    ElemSet key;
    int order, n, m, i;

    scanf("%d %d", &order, &n);
    btree = InitBTree(order);
    for (i = 0; i < n; i++) {
        scanf("%d", &key);
        x = (TElemSet)malloc(sizeof(Records));
        x->key = key;
        btree = InsertBTree(btree, x);
    }
    scanf("%d", &m);
    for (i = 0; i < m; i++) {
        scanf("%d", &key);
        x = SearchBTree(btree, key);
        if (x != NULL) {
            printf("%d\n", x->key);
        } else {
            printf("Not Found\n");
        }
    }

    return 0;
}
/* 你的代码将被嵌在这里 */

Position FindLeaf(BTreeHead btree, ElemSet key) {
    BTree current = btree->root;
    
    // 如果树为空，返回 NULL
    if (current == NULL) {
        return NULL;
    }
    
    // 从根结点开始向下查找
    while (!current->leaf) {
        int i = 0;
        // 在当前结点中找到第一个大于或等于 key 的关键码
        while (i < current->num_keys && key >= current->data[i]->key) {
            i++;
        }
        // 移动到相应的子结点
        current = current->children[i];
    }
    
    return current;
}

TElemSet SearchBTree(BTreeHead btree, ElemSet key) {
    // 找到包含 key 的叶结点
    Position leaf = FindLeaf(btree, key);
    
    // 如果叶结点为空，返回 NULL
    if (leaf == NULL) {
        return NULL;
    }
    
    // 在叶结点中查找 key
    for (int i = 0; i < leaf->num_keys; i++) {
        if (leaf->data[i]->key == key) {
            return leaf->data[i];
        }
    }
    
    // 如果未找到，返回 NULL
    return NULL;
}